package com.learn._2list;

import com.learn.TestTool;

import java.util.Random;

/**
 * 单链表list
 *
 * 和数组list比，依赖于下标的增删改查都需要额外付出n的代价，如果使用双链表，可以进行优化,在更偏向结束时从后面轮询到前面。
 *
 * contains效率一致
 *
 * 查找后的remove由于不用移位，效率更高
 *
 *
 * @param <T>
 */
public class SingleLinkedList<T> implements List<T> {

    //头结点一开始就创建，为虚拟节点，这样在size变到0时不用做额外判空，减少不必要开销
    private SingleLinkNode<T> head = new SingleLinkNode<>();
    private SingleLinkNode<T> last = head;
    private int curr;


    private class SingleLinkNode<T>{
        T value;
        SingleLinkNode<T> next;
    }


    public SingleLinkedList(){

    }


    /**
     *
     * @param idx
     * @return
     */
    @Override
    public T get(int idx) {
        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        SingleLinkNode<T> res = head;
        while(idx -- >=0){
            res = res.next;
        }
        return res.value;
    }

    @Override
    public int indexOf(T obj) {

        if(obj == null){
            return -1;
        }
        SingleLinkNode tmp = head;
        int idx = -1;
        while(tmp.next != null){
            tmp = tmp.next;
            idx ++;
            if(obj.equals(tmp.value)){
                return idx;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(T obj) {
        return indexOf(obj) != -1;
    }

    @Override
    public boolean empty() {
        return size() == 0;
    }

    @Override
    public int size() {
        return curr;
    }

    @Override
    public void add(T obj) {
        SingleLinkNode<T> newNode = new SingleLinkNode<>();
        newNode.value = obj;
        last.next = newNode;
        last = newNode;
        curr ++;
    }

    /**
     * linked list不用移，但是需要找                      双链表可以倒着找优化
     * @param idx
     * @param obj
     */
    @Override
    public void add(int idx, T obj) {

        if(idx > curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        if(idx == curr){
            add(obj);
        }else{

            SingleLinkNode tmp = findIdxPreNode(idx);
            insertAfter(tmp,obj);
            curr ++;
        }
    }

    private SingleLinkNode<T> findIdxPreNode(int idx) {
        SingleLinkNode<T> tmp = head;
        int tmpIdx = 0;
        while(tmp.next != null){
            if(tmpIdx == idx){
                break;
            }
            tmp = tmp.next;
            tmpIdx ++;
        }
        return tmp;
    }

    //保证tmp一定有后置
    private void insertAfter(SingleLinkNode tmp, T obj) {
        SingleLinkNode<T> newNode = new SingleLinkNode<>();
        newNode.value = obj;

        newNode.next = tmp.next;
        tmp.next = newNode;
    }


    /**
     * linked list不用移，但是需要找
     *
     * @param obj
     */
    @Override
    public void remove(T obj) {

        SingleLinkNode father = null;
        SingleLinkNode tmp = head;
        boolean remove = false;
        while(tmp.next!= null){
            father = tmp;
            tmp = tmp.next;
            if(obj.equals(tmp.value)){
                remove = true;
                break;
            }
        }
        if(remove) {
            removeAfter(father);
            curr --;
        }
    }

    @Override
    public void remove(int idx) {

        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        SingleLinkNode<T> preNode = findIdxPreNode(idx);
        removeAfter(preNode);
        curr --;
    }

    private void removeAfter(SingleLinkNode<T> preNode) {
        if(preNode.next.next == null){
            last = preNode;
        }
        preNode.next = preNode.next.next;
        //该节点在java中自动释放
    }

    @Override
    public void set(int idx, T obj) {

        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        SingleLinkNode<T> preNode = findIdxPreNode(idx);
        preNode = preNode.next;
        preNode.value = obj;
    }

    @Override
    public void clear() {
        head.next = null;
        last = head;
        curr = 0;
    }



    public static void main(String[] args) {
        java.util.LinkedList javaList = new java.util.LinkedList<>();
        SingleLinkedList arrayList = new SingleLinkedList();


        int num = 100000;
        int range = 1000000;
        int circleNum = 100;
        Integer[] array = new Integer[num];
        Random rand = new Random();
        int tmp = 0;
        int tmpNum = num;
        while(tmpNum -- > 0){
            array[tmp ++] = rand.nextInt(range);
        }

        for(Integer i :array){
            javaList.add(i);
            arrayList.add(i);
        }


        //查找测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.contains(i);
            }
        },1,"java contains ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.contains(i);
            }
        },1,"my contains ");*/


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num >> 1;i ++){
                arrayList.get(i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num >> 1;i ++){
                javaList.get(i);
            }
        },1,"java ");

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.indexOf(i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.indexOf(i);
            }
        },1,"java ");*/

        //增测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.add(i);
            }
            for(int i = 0;i < circleNum; i ++){
                javaList.add(i,i);
            }
        },1,"java ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.add(i);
            }
            for(int i = 0;i < circleNum; i ++){
                arrayList.add(i,i);
            }
        },1,"my  ");*/






        //修改测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.add(i);
            }
            for(int i = 0;i < num; i ++){
                arrayList.set(i,i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.add(i);
            }
            for(int i = 0;i < num; i ++){
                javaList.set(i,i);
            }
        },1,"java ");*/



        //删测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num; i ++){
                javaList.add(i);
            }

            for(int i = 0;i < num; i ++){
                javaList.remove(new Integer(i));
            }
            javaList.clear();
        },1,"java ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num; i ++){
                arrayList.add(i);
            }

            for(int i = 0;i < num; i ++){
                arrayList.remove(new Integer(i));
            }
            arrayList.clear();
        },1,"my  ");*/








    }

}
